#!/usr/bin/env python
# encoding: utf-8
"""
@author: shura
@position: saber
@contact: 2209032305@qq.com
@file: 131parition.py
@time: 2019/3/14 14:51
@desc:
"""
class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        res = []

        def dfs(ss, cur):
            if ss == ss[::-1]:
                res.append(cur+[ss])
            for i in range(1, len(ss)):
                if ss[:i] == ss[:i][::-1]:
                    dfs(ss[i:], cur+[ss[:i]])
        dfs(s, [])
        return res

s = Solution()
print(s.partition("babab"))